package org.hhchat.leetcode.dp;

/**
 * Created by HMH on 2017/3/30.
 */
public class code416 {
    public static class Solution {
        public boolean canPartition(int[] nums) {
            int len = nums.length;
            int sum=0;
            for(int i=0;i<len;i++) {
                sum += nums[i];
            }
            if(sum%2!=0) return false;
            int half = sum/2;
            boolean dp[] = new boolean[half+1];
            dp[0] = true;
            for(int i=1;i<=len;i++) {
                for(int j=half;j>=nums[i-1];j--) {
                    dp[j]=dp[j]||dp[j-nums[i-1]];
                }
            }
            return dp[half];
        }
    }

    public static void main(String[] args){
        System.out.println(new Solution().canPartition(new int[]{17,58,41,75,61,70,52,7,38,11,40,58,44,45,4,81,67,54,79,80,15,3,14,16,9,66,69,41,72,37,28,3,33,90,56,12,72,49,35,22,49,27,49,82,41,77,100,82,18,95,24,51,37,2,34,82,70,53,73,32,90,98,81,22,73,76,79,40,27,62,45,96,36,15,63,28,54,88,63,37,58,9,62,98,93,72,99,53,91,29,61,31,11,42,20,35,50,68,10,86}));
    }
}
